/*
 * $Id: stdlib_bitcount.c,v 1.3 2005-09-23 05:06:25 bacon Exp $
 */

#include <xp/bas/stdlib.h>

static int __bit_count[] = 
{
	/*   0 */ 0,
	/*   1 */ 1,
	/*   2 */ 1,
	/*   3 */ 2,
	/*   4 */ 1,
	/*   5 */ 2,
	/*   6 */ 2,
	/*   7 */ 3,
	/*   8 */ 1,
	/*   9 */ 2,
	/*  10 */ 2,
	/*  11 */ 3,
	/*  12 */ 2,
	/*  13 */ 3,
	/*  14 */ 3,
	/*  15 */ 4,
	/*  16 */ 1,
	/*  17 */ 2,
	/*  18 */ 2,
	/*  19 */ 3,
	/*  20 */ 2,
	/*  21 */ 3,
	/*  22 */ 3,
	/*  23 */ 4,
	/*  24 */ 2,
	/*  25 */ 3,
	/*  26 */ 3,
	/*  27 */ 4,
	/*  28 */ 3,
	/*  29 */ 4,
	/*  30 */ 4,
	/*  31 */ 5,
	/*  32 */ 1,
	/*  33 */ 2,
	/*  34 */ 2,
	/*  35 */ 3,
	/*  36 */ 2,
	/*  37 */ 3,
	/*  38 */ 3,
	/*  39 */ 4,
	/*  40 */ 2,
	/*  41 */ 3,
	/*  42 */ 3,
	/*  43 */ 4,
	/*  44 */ 3,
	/*  45 */ 4,
	/*  46 */ 4,
	/*  47 */ 5,
	/*  48 */ 2,
	/*  49 */ 3,
	/*  50 */ 3,
	/*  51 */ 4,
	/*  52 */ 3,
	/*  53 */ 4,
	/*  54 */ 4,
	/*  55 */ 5,
	/*  56 */ 3,
	/*  57 */ 4,
	/*  58 */ 4,
	/*  59 */ 5,
	/*  60 */ 4,
	/*  61 */ 5,
	/*  62 */ 5,
	/*  63 */ 6,
	/*  64 */ 1,
	/*  65 */ 2,
	/*  66 */ 2,
	/*  67 */ 3,
	/*  68 */ 2,
	/*  69 */ 3,
	/*  70 */ 3,
	/*  71 */ 4,
	/*  72 */ 2,
	/*  73 */ 3,
	/*  74 */ 3,
	/*  75 */ 4,
	/*  76 */ 3,
	/*  77 */ 4,
	/*  78 */ 4,
	/*  79 */ 5,
	/*  80 */ 2,
	/*  81 */ 3,
	/*  82 */ 3,
	/*  83 */ 4,
	/*  84 */ 3,
	/*  85 */ 4,
	/*  86 */ 4,
	/*  87 */ 5,
	/*  88 */ 3,
	/*  89 */ 4,
	/*  90 */ 4,
	/*  91 */ 5,
	/*  92 */ 4,
	/*  93 */ 5,
	/*  94 */ 5,
	/*  95 */ 6,
	/*  96 */ 2,
	/*  97 */ 3,
	/*  98 */ 3,
	/*  99 */ 4,
	/* 100 */ 3,
	/* 101 */ 4,
	/* 102 */ 4,
	/* 103 */ 5,
	/* 104 */ 3,
	/* 105 */ 4,
	/* 106 */ 4,
	/* 107 */ 5,
	/* 108 */ 4,
	/* 109 */ 5,
	/* 110 */ 5,
	/* 111 */ 6,
	/* 112 */ 3,
	/* 113 */ 4,
	/* 114 */ 4,
	/* 115 */ 5,
	/* 116 */ 4,
	/* 117 */ 5,
	/* 118 */ 5,
	/* 119 */ 6,
	/* 120 */ 4,
	/* 121 */ 5,
	/* 122 */ 5,
	/* 123 */ 6,
	/* 124 */ 5,
	/* 125 */ 6,
	/* 126 */ 6,
	/* 127 */ 7,
	/* 128 */ 1,
	/* 129 */ 2,
	/* 130 */ 2,
	/* 131 */ 3,
	/* 132 */ 2,
	/* 133 */ 3,
	/* 134 */ 3,
	/* 135 */ 4,
	/* 136 */ 2,
	/* 137 */ 3,
	/* 138 */ 3,
	/* 139 */ 4,
	/* 140 */ 3,
	/* 141 */ 4,
	/* 142 */ 4,
	/* 143 */ 5,
	/* 144 */ 2,
	/* 145 */ 3,
	/* 146 */ 3,
	/* 147 */ 4,
	/* 148 */ 3,
	/* 149 */ 4,
	/* 150 */ 4,
	/* 151 */ 5,
	/* 152 */ 3,
	/* 153 */ 4,
	/* 154 */ 4,
	/* 155 */ 5,
	/* 156 */ 4,
	/* 157 */ 5,
	/* 158 */ 5,
	/* 159 */ 6,
	/* 160 */ 2,
	/* 161 */ 3,
	/* 162 */ 3,
	/* 163 */ 4,
	/* 164 */ 3,
	/* 165 */ 4,
	/* 166 */ 4,
	/* 167 */ 5,
	/* 168 */ 3,
	/* 169 */ 4,
	/* 170 */ 4,
	/* 171 */ 5,
	/* 172 */ 4,
	/* 173 */ 5,
	/* 174 */ 5,
	/* 175 */ 6,
	/* 176 */ 3,
	/* 177 */ 4,
	/* 178 */ 4,
	/* 179 */ 5,
	/* 180 */ 4,
	/* 181 */ 5,
	/* 182 */ 5,
	/* 183 */ 6,
	/* 184 */ 4,
	/* 185 */ 5,
	/* 186 */ 5,
	/* 187 */ 6,
	/* 188 */ 5,
	/* 189 */ 6,
	/* 190 */ 6,
	/* 191 */ 7,
	/* 192 */ 2,
	/* 193 */ 3,
	/* 194 */ 3,
	/* 195 */ 4,
	/* 196 */ 3,
	/* 197 */ 4,
	/* 198 */ 4,
	/* 199 */ 5,
	/* 200 */ 3,
	/* 201 */ 4,
	/* 202 */ 4,
	/* 203 */ 5,
	/* 204 */ 4,
	/* 205 */ 5,
	/* 206 */ 5,
	/* 207 */ 6,
	/* 208 */ 3,
	/* 209 */ 4,
	/* 210 */ 4,
	/* 211 */ 5,
	/* 212 */ 4,
	/* 213 */ 5,
	/* 214 */ 5,
	/* 215 */ 6,
	/* 216 */ 4,
	/* 217 */ 5,
	/* 218 */ 5,
	/* 219 */ 6,
	/* 220 */ 5,
	/* 221 */ 6,
	/* 222 */ 6,
	/* 223 */ 7,
	/* 224 */ 3,
	/* 225 */ 4,
	/* 226 */ 4,
	/* 227 */ 5,
	/* 228 */ 4,
	/* 229 */ 5,
	/* 230 */ 5,
	/* 231 */ 6,
	/* 232 */ 4,
	/* 233 */ 5,
	/* 234 */ 5,
	/* 235 */ 6,
	/* 236 */ 5,
	/* 237 */ 6,
	/* 238 */ 6,
	/* 239 */ 7,
	/* 240 */ 4,
	/* 241 */ 5,
	/* 242 */ 5,
	/* 243 */ 6,
	/* 244 */ 5,
	/* 245 */ 6,
	/* 246 */ 6,
	/* 247 */ 7,
	/* 248 */ 5,
	/* 249 */ 6,
	/* 250 */ 6,
	/* 251 */ 7,
	/* 252 */ 6,
	/* 253 */ 7,
	/* 254 */ 7,
	/* 255 */ 8
};

int xp_bitcount (void* num, xp_size_t size)
{
	xp_byte_t* p, * end;
	int count = 0;

	p = (xp_byte_t*)num; end = p + size;
	while (p < end) count += __bit_count[*p++];
	return count;
}


/*

 http://www-db.stanford.edu/~manku/bitcount/bitcount.html

 1. Sparse Ones

 int bitcount (unsigned int n)  
 {  
     int count=0 ;
     while (n)
     {
        count++ ;
        n &= (n - 1) ;
     }
     return count ;
 }

 2. Dense Onces
 int bitcount (unsigned int n)     
 {
      int count = 8 * sizeof(int) ;
      n ^= (unsigned int) -1 ;
      while (n)
      {
         count-- ;
         n &= (n - 1) ;
      }
      return count ;
 }

 3. Parallel Count
 #define TWO(c)     (0x1u << (c))
 #define MASK(c)    (((unsigned int)(-1)) / (TWO(TWO(c)) + 1u))
 #define COUNT(x,c) ((x) & MASK(c)) + (((x) >> (TWO(c))) & MASK(c))
    
 int bitcount (unsigned int n)
 {
    n = COUNT(n, 0) ;
    n = COUNT(n, 1) ;
    n = COUNT(n, 2) ;
    n = COUNT(n, 3) ;
    n = COUNT(n, 4) ;
    // n = COUNT(n, 5) ;    for 64-bit integers 
    return n ;
 }

 Parallel Count carries out bit counting in a parallel fashion. 
 Consider n after the first line has finished executing. Imagine 
 splitting n into pairs of bits. Each pair contains the number of 
 ones in those two bit positions in the original n. After the second 
 line has finished executing, each nibble contains the number of ones 
 in those four bits positions in the original n. Continuing this for 
 five iterations, the 64 bits contain the number of ones among these
 sixty-four bit positions in the original n. That is what we wanted 
 to compute. 

 4. Nifty Parallel Count  
 #define MASK_01010101 (((unsigned int)(-1))/3)
 #define MASK_00110011 (((unsigned int)(-1))/5)
 #define MASK_00001111 (((unsigned int)(-1))/17)

 int bitcount (unsigned int n)
 {
    n = (n & MASK_01010101) + ((n >> 1) & MASK_01010101) ; 
    n = (n & MASK_00110011) + ((n >> 2) & MASK_00110011) ; 
    n = (n & MASK_00001111) + ((n >> 4) & MASK_00001111) ; 
    return n % 255 ;
 }

 5. MIT Hackmem Count
 int bitcount(unsigned int n)                          
 {
    // works for 32-bit numbers only   
    // fix last line for 64-bit numbers 
    
    register unsigned int tmp;
    
    tmp = n - ((n >> 1) & 033333333333)
            - ((n >> 2) & 011111111111);
    return ((tmp + (tmp >> 3)) & 030707070707) % 63;
 }

 MIT Hackmem Count is funky. Consider a 3 bit number as being 4a+2b+c.
 If we shift it right 1 bit, we have 2a+b. Subtracting this from the
 original gives 2a+b+c. If we shift the original 2 bits right we get a,
 and so with another subtraction we have a+b+c, which is the number of
 bits in the original number. How is this insight employed? The first
 assignment statement in the routine computes tmp. Consider the octal
 representation of tmp. Each digit in the representation is simply the
 number of 1's in the corresponding three bit positions in n. The last
 return statement sums these octal digits to produce the final answer.
 The key idea is to add adjacent pairs of octal digits together and then
 compute the remainder modulus 63. This is accomplished by right-shifting
 tmp by three bits, adding it to tmp itself and ANDing with a suitable mask. 
 This yields a number in which groups of six adjacent bits (starting from
 the LSB) contain the number of 1's among those six positions in n. This
 number modulo 63 yields the final answer. For 64-bit numbers, we would 
 have to add triples of octal digits and use modulus 1023. This is 
 HACKMEM 169, as used in X11 sources. Source: MIT AI Lab memo, late 1970's.
 
*/
